﻿//5. 最长回文子串
//给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        if (n < 2)    return s;
        int maxlen = 1, begin = 0;;
        vector<vector<bool>> dp(n, vector<bool>(n));    //以s[i]结尾的最长回文串长度
        for (int i = 0; i < n; i++)    dp[i][i] = true;
        for (int len = 2; len <= n; len++)
        {
            for (int left = 0; left < n; left++)
            {
                int right = left + len - 1;
                if (right >= n) break;
                if (s[left] != s[right])
                {
                    dp[left][right] = false;
                }
                else
                {
                    if (right - left < 3)  dp[left][right] = true;
                    else  dp[left][right] = dp[left + 1][right - 1];
                }
                if (dp[left][right] && right - left + 1 > maxlen)
                {
                    maxlen = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};